package com.lun.swordtowardoffer2.c14;

public class IsInterleave {

	
	public boolean isInterleave(String str1, String str2, String str3) {
		
		int len1 = str1.length(), len2 = str2.length();
		if(len1 + len2 != str3.length()) {
			return false;
		}
		
		boolean[][] dp = new boolean[len1 + 1][len2 + 1];
		
		dp[0][0] = true;
		
		for(int i = 0; i < len1; i++) {
			dp[i + 1][0] = str1.charAt(i) == str3.charAt(i) && dp[i][0];
		}
		
		for(int j = 0; j < len2; j++) {
			dp[0][j + 1] = str2.charAt(j) == str3.charAt(j) && dp[0][j];
		}
		
		for(int i = 0; i < len1; i++) {
			for(int j = 0; j < len2; j++) {
				char ch1 = str1.charAt(i);
				char ch2 = str2.charAt(j);
				char ch3 = str3.charAt(i + j + 1);
				
				dp[i + 1][j + 1] = (ch1 == ch3 && dp[i][j + 1])// 
						|| (ch2 == ch3 && dp[i + 1][j]);  
				
			}
		}
		
		return dp[len1][len2];
	}
	
	//优化空间效率
	public boolean isInterleave2(String str1, String str2, String str3) {
		
		int len1 = str1.length(), len2 = str2.length();
		if(len1 + len2 != str3.length()) {
			return false;
		}
		
		if(len1 > len2) {
			return isInterleave2(str2, str1, str3);
		}
		
		boolean[] dp = new boolean[len2 + 1];
		
		dp[0] = true;
		
		for(int j = 0; j < len2; j++) {
			dp[j + 1] = str1.charAt(j) == str3.charAt(j) && dp[j];
		}
		
		for(int i = 0; i < len1; i++) {
			
			dp[0] = str1.charAt(i) == str3.charAt(i) && dp[0];
			
			for(int j = 0; j < len2; j++) {
				char ch1 = str1.charAt(i);
				char ch2 = str2.charAt(j);
				char ch3 = str3.charAt(i + j + 1);
				
				dp[j + 1] = (ch1 == ch3 && dp[j + 1])// 
						|| (ch2 == ch3 && dp[j]);  
				
			}
		}
		
		return dp[len2];
	}
	
}
